package 剑指Offer43.a1n整数中1出现的次数;

/**
 * 2304
 * 假设当前位（十位）取1，
 * 当cur=0时，个数=（23）*10，前面最多取22，231*会大于2304
 * 2314
 * 当cur=1时，个数=（23+1）*（4+1）
 * 2324
 * 当cur>1时，个数=（23+1）*10
 * <p>
 * 因为只算了当前位的1的个数，所以不会重复计算
 * <p>
 * 假设十位的权因子 digit=10
 * 那么高位的值为 high=n/(d*10)
 * 低位的值为 low=n%d
 * <p>
 * <p>
 * <p>
 * * 2304
 * * 假设当前digit=10，
 * * 当cur=0时，个数=high*digit，前面最多取22，231*会大于2304
 * * 2314
 * * 当cur=1时，个数=（high+1）*（low+1）
 * * 2324
 * * 当cur>1时，个数=（high+1）*digit
 * <p>
 * *  * 2300
 * *  * 假设当前digit=1，
 * *  * 当cur=0时，个数=high*digit，前面最多取22，231*会大于2304
 * *  * 2301
 * *  * 当cur=1时，个数=（high+1）*（low+1）
 * *  * 2301
 * *  * 当cur>1时，个数=（high+1）*digit
 * <p>
 */

/**
 * case 1: cur=0
 * 2  3   0  4
 * 千位和百位可以选00 01 02....22  十位可以取到1( 形如[00|01..|22]1[0-9] 都是<2304 ) 个位可以选0-9  共有 23 * 10 中排列
 * 当千位和百位取23,如果十位取1 那就是形如 231[0-9] > 2304,所以当千位和百位取23，十位只能能取0，个位取0-4即 2300 2301 2302 2303 2304
 * 但是2301不应该算进来，这个1是 单独  出现在个位的（而11，121,111这种可以被算多次）
 * 即 23*10
 * <p>
 * case 2: cur=1
 * 2  3  1  4
 * 千位和百位可以选00 01 02....22  十位可以取到1 个位可以选0-9  共有 23 * 10 中排列
 * 当千位和百位取23,十位取1，个位可以去0-4 即 2310-2314共5个
 * 即 23 *10 + 4 +1
 * <p>
 * case 3: cur>1 即2-9
 * 2  3  2  4
 * 千位和百位可以选00 01 02....23  十位可以取到1(形如 [00|01...|22]1[0-9] 都是<2324) 个位可以选0-9  共有 23 * 10 中排列
 * 即 （23+1） *10
 */

/**
 * 时间：O（logn） n包含的数位个数与n呈对数关系
 * 空间：O(1)
 */
public class Solution2 {
    public int countDigitOne(int n) {
        int len = 0, t = n;
        while (t > 0) {
            len++;
            t /= 10;
        }
        int digit = 1, ans = 0;
        for (int i = 0; i < len; i++) {
            int high = n / digit / 10, //小细节防止越界
                    low = n % digit,
                    cur = n / digit % 10;
            if (cur == 0) {
                ans += high * digit; // 2204  0-21，221*就大于n了
            } else if (cur == 1) {
                ans += high * digit + (low + 1); // 2214  0-21，0-9   22 0-4
            } else {
                ans += (high + 1) * digit; // 2234 0-22 -0-9
            }
            digit *= 10;
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        System.out.println(solution2.countDigitOne(1410065408));
    }
}
